#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (unsigned int i = 0; i < nums.size(); i++) sum += nums[i];
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    int dp[target + 1];
    memset(dp, 0, sizeof(dp));
    for (unsigned int i = 0; i < nums.size(); i++) {
        //再遍历容量，倒序遍历，注意！遍历的背包容量j是>=当前的物品的重量的。
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = fmax(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    if (dp[target] == target) {
        return true;
    } else {
        return false;
    }
}
int main(){

    vector<int> nums = {1, 2, 3, 5};

    cout << canPartition(nums) << endl;
    return 0;
}